//拓补排序
//用DFS解决问题
//先运行DFS得到postorder，postorder就是一个点已经访问完，并且其邻接点也都被访问过了，那就将其加入postorder
//运行完之后，用反向的postorder返回点
//拓补排序的前提是图中没有循环，所以在进行拓补排序之前需要先用DFS进行循环检测
//进行循环检测思路很简单，就是用DFS，如果一个点已经被mark过了，但是之后又被访问
//那么则检验要访问他的这个点是否是来自由他而来的路径上，如果是，那么说明有循环
//也就是说，添加一个正在栈上数组，如果一个点正在栈上，那么则加进去，如果一个点访问到了一个正在栈上的点，那么则说明出现了上面的情况，也就是存在循环
import edu.princeton.cs.algs4.*;
public class Topological_Sorting {
    private boolean marked[];
    private boolean onStack[];
    private Stack<Integer> reversePost;

    public Topological_Sorting(Digraph g)
    {
       marked=new boolean[g.V()];
       onStack=new boolean[g.V()];
       reversePost=new Stack<Integer>();
       for(int i=0;i<g.V();i++)
       {
          if(!marked[i])
          {
            Dfs(g,i);
          }
       }
    }

    public void Dfs(Digraph g,int v)
    {
        marked[v]=true;
        onStack[v]=true;
        for(int i:g.adj(v))
        {
            if(onStack[i])
            {
                System.err.println("circle!");
            }
           if(!marked[i])
           {
            Dfs(g,i);
           }
        }
        reversePost.push(v);
        onStack[v]=false;
    }

    public Iterable<Integer> ReversePost()
    {
        return reversePost;
    }

}
